package q695_maxAreaOfIsland;

public class Solution_1 {
    // 四个方向
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, 1, -1, 0};
    int maxArea = 0;// 最大面积
    int tempArea = 0;// 用于记录当前岛屿统计到的面积
    /*
    参考733的二维平面搜索方法
    其中dfs的搜索是几乎一致的
     */
    public int maxAreaOfIsland(int[][] grid) {
        // 建立一个数组记录当前块是否已被统计
        boolean[][] marked = new boolean[grid.length][grid[0].length];
        // 需要遍历整个图
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1 && !marked[i][j]) {
                    tempArea = 0;// 每次开始搜索需要先重置temp
                    dfs(grid, marked, i, j);
                }

            }
        }

        return maxArea;
    }

    private void dfs(int[][] grid, boolean[][] marked, int r, int c) {
        // 确定终止条件
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0 || marked[r][c]) {
            maxArea = Math.max(maxArea, tempArea);
            return;
        }

        // 符合条件的块 则进行对应操作
        marked[r][c] = true;
        tempArea++;

        // 向四个方向继续寻找
        for (int i = 0; i < 4; i++) {
            int next_r = r + dx[i], next_c = c + dy[i];
            dfs(grid, marked, next_r, next_c);
        }
    }
}
